package org.sunny.sort;

import org.sunny.tools.Integers;

/**
 * 插入排序
 *
 * 逆序对
 *  什么是逆序对？
 *  数组 <2,3,8,6,1> 的逆序对为：<2,1> <3,1> <8,1> <8,6> <6,1>，共5个逆序对
 *
 *  也就是左边的元素比右边的元素大,就算是一个逆序对
 *
 *  插入排序的时间复杂度与逆序对的数量成正比关系
 *  逆序对的数量越多，插入排序的时间复杂度越高
 *
 *  逆序对的数量极少时，插入排序的效率特别高
 *  甚至速度比 O nlogn 级别的快速排序还要快
 *
 * @author Sunny
 * @date 2020/8/20
 */
public class InsertionSort {

    public static void main(String[] args) {
        Integer[] arr = Integers.random(1000, 1, 1000);

        insertionSort3(arr);
        System.out.println(Integers.isAscOrder(arr));
    }

    /**
     * 插入排序优化
     *
     *  假设在 [begin, end) 范围内搜索某个元素 v，mid == (begin + end) / 2
     *  ◼ 如果 v < m，去 [begin, mid) 范围内二分搜索
     *  ◼ 如果 v ≥ m，去 [mid + 1, end) 范围内二分搜索
     *      因为二分搜索返回的插入位置：第1个大于 v 的元素位置
     *      所以 v ≥ m 这里条件多了个 = , 因为不保证后面是否还有相等的元素, 所以向后继续找
     *
     *  相比 insertionSort2 的优化在于减少了比较次数, 时间复杂度还是一样的
     *
     * @param arr 待排序数组
     * @author Sunny
     * @date 2020/8/21
     */
    public static void insertionSort3(Integer[] arr) {
        for (int begin = 1; begin < arr.length; begin++) {
            //找到当前元素应该插入的合适位置
            int insertIndex = searchIndex(arr, begin);

            //备份要插入的元素
            int v = arr[begin];

            //将 insertIndex - begin 的元素 向后挪动一位
            //从后面开始挪动
            for (int i = begin; i > insertIndex ; i--) {
                arr[begin] = arr[begin - 1];
            }

            //插入元素到合适位置
            arr[insertIndex] = v;
        }
    }

    /**
     * 利用二分搜索找出 v 应该在 arr 数组中插入的位置
     *  二分搜索返回的插入位置：第1个大于 v 的元素位置
     *
     * @param arr 有序数组
     * @param index 待插入元素的索引, 且其索引位置刚好是分割了前面已经排好序的部分数组的长度
     * @author Sunny
     * @date 2020/8/21
     */
    private static int searchIndex(Integer[] arr, int index) {
        int begin = 0;
        int end = index;

        while (begin < end) {
            int mid = (begin + end) >> 1;

            if (arr[index] < arr[mid]) {
                end = mid;
            } else {
                begin = mid + 1;
            }
        }
        return begin;
    }

    /**
     * 插入排序优化
     *
     *  思路是将【交换】转为【挪动】
     *  ① 先将待插入的元素备份
     *  ② 头部有序数据中比待插入元素大的，都朝尾部方向挪动1个位置
     *  ③ 将待插入元素放到最终的合适位置
     *
     * @param arr 待排序数组
     * @author Sunny
     * @date 2020/8/20
     */
    public static void insertionSort2(Integer[] arr) {
        for (int begin = 1; begin < arr.length; begin++) {
            //记录移动的索引, 一轮结束后, 从之前挪动元素的索引的下一个索引继续
            int cur = begin;

            //备份当前遍历到的元素值
            int v = arr[cur];
            //当前元素与前面的元素比较, 如果当前元素小, 直接用前面的元素覆盖掉当前索引的元素
            //优化点: 不再是每次都进行两两交换, 而是直接将元素较大的往后挪动, 节省交换的次数, 逆序对越多, 优化效果越明显
            while (cur > 0 && SortUtils.cmp(v, arr[cur - 1]) < 0) {
                arr[cur] = arr[cur - 1];
                cur--;
            }
            //当走到这, 说明cur的位置就是当前元素合适的位置
            arr[cur] = v;
        }
    }

    /**
     * 插入排序
     *  类似于扑克牌的插牌动作, 新加入的元素要移动到合适的位置
     *
     *  执行流程
     *  ① 在执行过程中，插入排序会将序列分为2部分
     *      ✓ 头部是已经排好序的，尾部是待排序的
     *  ② 从头开始扫描每一个元素
     *      ✓ 每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序
     *
     * @param arr 待排序数组
     * @author Sunny
     * @date 2020/8/20
     */
    public static void insertionSort1(Integer[] arr) {
        for (int begin = 1; begin < arr.length; begin++) {
            //记录移动的索引, 一轮结束后, 从之前挪动元素的索引的下一个索引继续
            int cur = begin;

            //不断的将新插入的元素向左移动, 插入到前面合适的位置
            while (cur > 0 && SortUtils.cmp(arr[cur], arr[cur - 1]) < 0){
                SortUtils.swap(arr, cur, cur - 1);
                cur--;
            }
        }
    }
}
